'''
钢条切割问题--重构解
    如何修改动态规划算法,使其不仅输出最优解,还输出最优切割方案:

    对每个子问题,保存切割一次时左边切下的长度
'''


def cut_rod_dp(p, n):
    """
    动态规划求解钢条切割问题（带切割方案）

    参数:
        p: 价格数组，p[i]表示长度为i的钢条的价格（索引从1开始有效）
        n: 需要切割的钢条总长度

    返回:
        tuple: (最大收益, 切割方案列表)
    """
    # r[i]表示长度为i的钢条的最大收益
    r = [0] * (n + 1)
    # s[i]记录长度为i的钢条的第一个切割长度（用于回溯方案）
    s = [0] * (n + 1)

    # 计算每个长度的最大收益和最佳切割位置
    for i in range(1, n + 1):
        max_profit = 0
        # 尝试所有可能的切割位置
        for j in range(1, i + 1):
            current_profit = p[j] + r[i - j]
            # 更新最大收益和切割位置
            if current_profit > max_profit:
                max_profit = current_profit
                s[i] = j  # 记录最佳切割位置,(第一刀的切割位置)
        r[i] = max_profit

    # 回溯切割方案


    切割方案 = []
    remaining = n  # 剩余长度
    while remaining > 0:
        切割长度 = s[remaining]  # 获取当前剩余长度的最佳切割
        切割方案.append(切割长度)
        remaining -= 切割长度  # 计算新的剩余长度

    return r[n], 切割方案

# 示例用法
if __name__ == "__main__":
    # 价格表：索引对应长度（0-10）
    price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

    # 测试不同长度
    for length in [4, 5, 7]:
        max_profit, solution = cut_rod_dp(price, length)
        print(f"钢条长度: {length}")
        print(f"最大收益: {max_profit}")
        print(f"切割方案: {solution}")
        print("-" * 50)
